package com.dyz.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;

public class LargestRectangleArea84 {
    public static void main(String[] args) {
        int[] heights = {2, 1, 5, 6, 2, 3};
        int i = new LargestRectangleArea84().largestRectangleArea1(heights);
        System.out.println(i);
    }
    public int largestRectangleArea(int[] heights) {
        //方法一：暴力解法 超时
        int len = heights.length;
        if(len==0){return 0;}

        int res = 0;
        for(int i=0; i<len; i++){

            int left = i;
            int curHeight = heights[i];
            //找左边最后1个大于等于heights[i]的下标
            while (left>0 && heights[left-1]>=curHeight){left--;}
            //找右边最后1个大于等于height[i]的索引
            int right = i;
            while (right<len-1 && heights[right+1]>=curHeight){right++;}

            int width = right - left +1;
            res = Math.max(res, width*curHeight);
        }
        return res;
    }
    //方法二：单调栈 加了哨兵的写法
    public int largestRectangleArea1(int[] heights) {

        int len = heights.length;
        if(len==0){return 0;}
        if(len==1){return heights[0];}
        //加入哨兵
        int [] newHeights = new int[len+2];
        newHeights[0] = 0;
        System.arraycopy(heights, 0, newHeights, 1, len);
        newHeights[len+1] = 0;
        len +=2;
        // 先放入哨兵，在循环里就不用做非空判断
        Deque<Integer> stack = new ArrayDeque<>();
        stack.add(0);
        int res = 0;
        heights = newHeights;
        for(int i=1; i<len; i++){
            while (heights[i] < heights[stack.peekLast()]){
                int curHeight = heights[stack.pollLast()];
                int curWidth = i - stack.peekLast()-1;
                res = Math.max(res, curWidth*curHeight);
            }
            stack.addLast(i);
        }

        return res;
    }
}
